package com.zyk.leetcode;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author zhangsan
 * @date 2021/4/13 20:10
 */
public class A_QuickSort {


    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process2(arr, 0, arr.length - 1);
    }

    public static void process2(int[] arr, int l, int r) {
        // base case
        if (l == r) {
            return;
        }
        int mid = l + ((r - l) >> 1);
        process2(arr, l, mid);
        process2(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    public static void merge(int[] arr, int l, int mid, int r) {
        int[] help = new int[r - l + 1];
        int index = 0, lIndex = l, rIndex = mid + 1;  // index 辅助数组的赋值下标， lIndex：左边下标，rIndex：右边下标
        while (lIndex <= mid && rIndex <= r) {
            help[index++] = arr[lIndex] < arr[rIndex] ? arr[lIndex++] : arr[rIndex++];
        }
        // 此时上边循环结束，有两种情况。
        // 1：lIndex 越界
        // 2：rIndex 越界
        while (lIndex <= mid) {
            help[index++] = arr[lIndex++];
        }
        while (rIndex <= r) {
            help[index++] = arr[rIndex++];
        }
        // 最后把辅助数组给 拷贝到 数组里
        do {
            arr[r] = help[--index];
            r--;
        } while (r >= l);
    }

    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2)
            return;
        process(arr, 0, arr.length - 1);
    }

    private static void process(int[] arr, int l, int r) {
        if (l == r)
            return;
        int pivot = arr[(int) (Math.random() * (r - l)) + 1 + l];
        int[] range = partition(arr, l, r, pivot);
        if (l != range[0])
            process(arr, l, range[0] - 1);
        if (r != range[1])
            process(arr, range[1] + 1, r);
    }

    /**
     * 在数组的[L ~ R], 分区过程, 左边都比pivot小, 中间都是等于他, 右边都比他大
     *
     * @param arr   数组
     * @param pivot 中心数
     */
    public static int[] partition(int[] arr, int l, int r, int pivot) {
        int leftBorder = l - 1, rightBorder = r + 1, curIndex = l;
        while (curIndex < rightBorder) {
            if (arr[curIndex] < pivot)
                swap(arr, curIndex++, ++leftBorder);
            else if (arr[curIndex] == pivot)
                curIndex++;
            else
                swap(arr, curIndex, --rightBorder);
        }
        return new int[]{leftBorder + 1, rightBorder - 1};
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void selectSort(int[] arr) {
        int min;
        for (int i = 0; i < arr.length - 1; i++) {
            min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[min] > arr[j]) {
                    min = j;
                }
            }
            swap(arr, i, min);
        }
    }

    public static int[] generateArr(int maxLen, int maxValue, boolean fixedSize, boolean hasMinus) {
//        if (Math.random() < 0.1) return null; //0.1的概率return null
        maxLen = fixedSize ? maxLen : (int) (Math.random() * maxLen) + 1;
        int[] nums = new int[maxLen];
        for (int i = 0; i < maxLen; i++) {
            nums[i] = hasMinus ? (int) (Math.random() * maxValue) - (int) (Math.random() * maxValue) : (int) (Math.random() * maxValue);
        }
        return nums;
    }

    public static void heapSort(int[] arr) {
        PriorityQueue<Integer> smallHeap = new PriorityQueue<>();
        for (int i : arr) {
            smallHeap.add(i);
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] = smallHeap.poll();
        }
    }


    public static void main(String[] args) {
        /*int[] arr = {2, 5, 6, 3, 5, 8, 7, 4, 1, 2, 5};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));*/


       /* System.out.println("测试开始...");
        int times = 100000;
        int maxLen = 100;
        int maxValue = 132165321;
        for (int i = 0; i < times; i++) {
            int[] nums = generateArr(maxLen, maxValue, false, true);
            int[] nums1 = Arrays.copyOf(nums, nums.length);

            Arrays.sort(nums);
            quickSort(nums1);

            if(!Arrays.equals(nums, nums1)) {
                System.out.println("OOPS");
                break;
            }

        }
        System.out.println("测试结束...");*/
        /*for (int i = 10; i <= Integer.MAX_VALUE; i += 1000) {
            System.out.println("=================size: " + i + "=======================");
            int[] nums1 = generateArr(i, Integer.MAX_VALUE, true, true);
            int[] nums2 = Arrays.copyOf(nums1, nums1.length);
            int[] nums3 = Arrays.copyOf(nums1, nums1.length);
            int[] nums4 = Arrays.copyOf(nums1, nums1.length);

            long s1 = System.currentTimeMillis();
            quickSort(nums1);
//            long s2 = System.currentTimeMillis();
//            selectSort(nums2);
            long s3 = System.currentTimeMillis();
            Arrays.sort(nums3);
            long s4 = System.currentTimeMillis();
            mergeSort(nums4);
            long s5 = System.currentTimeMillis();

            if (!Arrays.equals(nums3, nums1) || !Arrays.equals(nums4, nums3)) {
                System.out.println("OOPS");
                break;
            }
//            System.out.println("选择排序O(N^): " + (s3 - s2));
//            System.out.println("快速排序(n*logN): " + (s2 - s1));
            System.out.println("快速排序(n*logN): " + (s3 - s1));
            System.out.println("系统排序: " + (s4 - s3));
            System.out.println("归并排序(n*logN): " + (s5 - s4));
            System.out.println("========================================");
        }*/
        int[] arr = {2, 5, 6, 3, 5, 8, 7, 4, 1, 2, 5};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));

    }

}
